\section{Illustration de la solution sur un exemple}

\begin{figure}
	{\small
	\begin{alltt}
		01:   CLASS Heater
		02:       control            : INT;
		03:       state              : BOOL;
		04:   END_CLASS
		05:   GLOBAL_VAR
		06:       heater             : Heater;
		07:       temperature        : INT;
		08:       fuel_cost          : INT;
		09:       maintenanceAlarm   : BOOL;
		10:       led                : BOOL;
		11:       smokeDetect        : BOOL;
		12:       fireAlarm          : BOOL;
		13:       sprinkler          : BOOL;
		14:   END_VAR
		15:   SEQUENCE set_heater (new_state : BOOL)
		16:       heater.state := new_state;
		17:       IF heater.state THEN
		18:           led        := TRUE;
		19:           fuel_cost  := fuel_cost + 10;
		20:       ELSE
		21:           led := FALSE;
		22:       END_IF
		23:       heater.control := heater.control + 1;
		24:   END_SEQUENCE
		25:   WHEN heater.control == 1000 THEN
		26:       control := 0;
		27:       maintenanceAlarm := TRUE;
		28:   END_WHEN
		29:   WHEN ~temperature < 0 THEN
		30:       IF (NOT maintenanceAlarm) THEN
		31:           LAUNCH set_heater(1);
		32:       END_IF
		33:   END_WHEN
		34:   WHEN ~temperature > 20 THEN
		35:       IF (NOT maintenanceAlarm) THEN
		36:           LAUNCH set_heater(0);
		37:       END_IF
		38:   END_WHEN
		39:   WHEN smokeDetect THEN
		40:       fireAlarm    := TRUE;
		41:       sprinkler    := TRUE;
		42:   END_WHEN
		43:  PROGRAM
		44:      heater.control := 0;
		45:      LAUNCH set_heater(temperature < 0);
		46:  END_PROGRAM
	\end{alltt}
	}
	\caption{Le code \textsl{dSL} du nouveau programme}
	\label{figDSLExampleRedistrib01}
\end{figure}

Afin de bien illustrer l'idée de la technique de redistribution, l'exemple de la section~\ref{dslProgExample} sera modifié et redistribué. Les modifications qui seront apportées n'auront pas toujours un sens dans la réalité, mais il s'agit principalement de modifications pour permettre de voir la plupart des cas de la redistribution. \\

Imaginons que l'on veuille ajouter un système de détection de feu dans notre contrôle. Il nous faudrait donc avoir un détecteur de fumée ainsi qu'un actionneur d'alarme et un \textsl{sprinkleur} (appelé parfois ``tête d'extinction automatique à eau'', ``gicleur d'incendie'' ou ``asperseur''). Ce détecteur et ces deux actionneurs seront contrôlés par la même carte, différente de celle qui contrôle le chauffage. Cette modification introduira trois nouvelles variables, \texttt{smokeDetect}, \texttt{fireAlarm} et \texttt{sprinkler}. Toutes les trois seront ajoutées dans la nouvelle table de localisation en les assignant au nouveau site ajouté. En plus de cet ajout de n\oe{}uds et de contraintes, on peut imaginer supprimer la contrainte de localisation de la variable \texttt{led} (sans avoir de réel sens, cela permet d'avoir une suppression de contraintes). Enfin, on peut imaginer faire fonctionner le code sans la variable \texttt{maintenance}, en modifiant le code comme suit: l'instruction 25 fera en sorte d'activer directement l'alarme, ce qui implique que le \texttt{WHEN} de la ligne 27 n'est plus utile et que les \texttt{IF} des lignes 31 et 36 doivent se baser sur l'état de l'alarme au lieu de l'état de la maintenance. Le n\oe{}ud \texttt{maintenance} sera donc supprimé et les n\oe{}uds des instructions qui l'utilisaient seront modifiés. Une dernière modification que l'on pourrait imaginer serait de renommer la variable \texttt{alarm} en \texttt{maintenanceAlarm} afin d'avoir un code plus précis. Résumons les modifications apportées: \\

\begin{itemize}
	\item Ajout de \texttt{fireAlarm}, de \texttt{smokeDetect} et de \texttt{sprinkler} (ainsi que les instructions qui les utilisent)
	\item Ajout des contraintes sur \texttt{fireAlarm}, \texttt{smokeDetect} et \texttt{sprinkler}.
	\item Suppression de la contrainte sur \texttt{led}
	\item Suppression de la variable \texttt{maintenance}
	\item Modification des instructions qui utilisaient \texttt{maintenance}
	\item Modification du nom de \texttt{alarm} en \texttt{maintenanceAlarm} (ce qui implique une modification des instructions qui utilisaient cette variable)
\end{itemize}

\bigskip
\noindent
Le code de cette nouvelle version de l'application se retrouve en figure~\ref{figDSLExampleRedistrib01}. \\

Pour cette application, nous avons trois sites, que nous nommerons $S_{cpanel}$ pour le panneau de contrôle, $S_{heater}$ pour le chauffage et $S_{fire}$ pour l'alarme incendie. La table de localisation pour ce programme est donnée ci-dessous: \\

\begin{center}
\begin{tabular}{|l|l|l|}
	\hline
	\textbf{Variables} & \textbf{Sites} & \textbf{Couleurs} \\
	\hline
	\texttt{state} & $S_{heater}$ & {\color{Red}Rouge} \\
	\hline
	\texttt{temperature} & $S_{heater}$ & {\color{Red}Rouge} \\
	\hline
	\texttt{maintenanceAlarm} & $S_{cpanel}$ & {\color{ForestGreen}Vert} \\
	\hline
	\texttt{smokeDetect} & $S_{fire}$ & {\color{Orange}Orange} \\
	\hline
	\texttt{fireAlarm} & $S_{fire}$ & {\color{Orange}Orange} \\
	\hline
	\texttt{sprinkler} & $S_{fire}$ & {\color{Orange}Orange} \\
	\hline
\end{tabular}
\end{center}

\bigskip
Donc, avant de commencer à comparer les deux versions ou de colorer quoi que ce soit, il faut créer le graphe de l'application. Une fois ce graphe créé, on peut passer au pré-traitement qui consiste à colorer les n\oe{}uds pour lesquels on n'a pas le choix. En fait, il suffit de parcourir la table de localisation, de colorer les n\oe{}uds représentant les variables et, ensuite, de regarder tous les liens (directs ou indirects) entre les n\oe{}uds déjà colorés et des n\oe{}uds incolores du graphe et colorer ceux-ci dans la couleur du n\oe{}ud auquel ils sont reliés. Ce pré-traitement nous donne un graphe partiellement coloré, comme représenté en figure~\ref{figRedistribEx02}. \\

\begin{figure}[!ht]
	\begin{center}
		\includegraphics[scale=0.5]{Images/figRedistribEx02.pdf}
		\caption{Le graphe du nouveau code après le pré-traitement}
		\label{figRedistribEx02}
	\end{center}
\end{figure}

\bigskip
Ensuite, nous pourrons passer à la comparaison des graphes des deux versions. Pour ce faire, il nous faut d'abord enlever les n\oe{}uds dont on est certain qu'ils ne pourront pas être re-colorés, c'est-à-dire les n\oe{}uds sur lesquels une contrainte (directe ou indirecte) de couleur est imposée. Les graphes simplifiés de l'ancienne et de la nouvelle version qu'il faudra comparer sont représentés en haut de la figure~\ref{figRedistribEx03}. La comparaison se fait à l'aide de l'algorithme présenté en section~\ref{vf2Algo}. Le bas de la figure~\ref{figRedistribEx03} représente les trois étapes nécessaires pour calculer le \textsl{mapping} entre les deux graphes. Détaillons ces étapes: \\

\begin{figure}[!ht]
	\begin{center}
		\includegraphics[scale=0.5]{Images/figRedistribEx03.pdf}
		\caption{L'ancienne et la nouvelle version des graphes simplifiés et les trois étapes de l'algorithme de comparaison}
		\label{figRedistribEx03}
	\end{center}
\end{figure}

\begin{description}
	\item[Première étape:] L'ensemble $s_0$ est vide, on calcule $P(s_0)$. Étant donné que $G_1(s)$ et $G_2(s)$ sont vides, $T^{in}_1$, $T^{out}_1$, $T^{in}_2$ et $T^{out}_2$ le sont également. Dès lors, $P(s_0)$ doit être calculé en prenant toutes les combinaisons des n\oe{}uds du premier et du second graphe. Chacune de ces paires est alors évaluée pour savoir si elle respecte les règles de faisabilité (syntaxique et sémantique). Il est facile de s'apercevoir que le couple $(17, 19)$ (l'instruction de la $17^{e}$ ligne de l'ancien code et l'instruction de la $19^{e}$ ligne du nouveau code) respecte ces règles et peut donc être inséré dans $M(s_1)$. 
	\item[Deuxième étape:] Il n'existe plus de paire possible puisque le premier graphe est totalement couvert. 
\end{description}

\bigskip
Le \textsl{mapping} $M$ possède deux paires, $\lbrace (17, 19), (fuel\_cost, fuel\_cost) \rbrace$, ce qui signifie que le n\oe{}ud $19$ et le n\oe{}ud $fuel\_cost$ du second graphe prennent respectivement la couleur du n\oe{}ud $17$ et de $fuel\_cost$, c'est-à-dire le vert. La comparaison étant finie, le \textsl{mapping} étant établi, il ne reste plus qu'à optimiser la fin de la coloration. \\

\begin{figure}[h]
	\begin{center}
		\includegraphics[scale=0.5]{Images/figRedistribEx05.pdf}
		\caption{Le graphe pour l'optimisation de la re-coloration}
		\label{figRedistribEx05}
	\end{center}
\end{figure}

La figure~\ref{figRedistribEx05} représente le graphe utilisé pour la re-coloration. Dans le but de pouvoir calculer les coûts et résoudre la re-coloration, il faut fixer certains paramètres, tels que les paramètres d'importance des coûts, $\alpha = 0,5$ et $\beta = 1$. Il faut également fixer les valeurs de probabilités du \texttt{IF}, $p = 0,5$, c'est-à-dire qu'il y a autant de chance d'aller dans une branche du \texttt{IF} que dans l'autre, et $\psi = 0,1$, c'est-à-dire qu'il y a 10\% de chance d'avoir une valeur inconnue dans l'évaluation d'une condition d'un \texttt{IF ... THEN ... ELSE ... END\_IF}. \\

Le problème est donc de trouver une assignation de couleur pour les n\oe{}uds des instructions aux lignes 18, 19, 21 et 23. Dans les schémas d'exécution de l'algorithme de séparation et d'évaluation qui vont suivre, une solution sera, par exemple, notée $ROVR$, ce qui signifie qu'on attribuera la couleur \textbf{r}ouge au n\oe{}ud 18, la couleur \textbf{o}range pour le n\oe{}ud 19, la couleur \textbf{v}erte au n\oe{}ud 21 et la couleur \textbf{r}ouge au n\oe{}ud 23. Les deux contraintes à respecter, ici, ce sont la couleur verte imposée au n\oe{}ud 23 et le fait que les n\oe{}uds 18 et 21 doivent avoir la même couleur. Rappelons que, au départ, le n\oe{}ud 19 possède la couleur vert, puisqu'il a été \textit{matché} dans l'étape de comparaison. \\

La première étape de la re-coloration est donc de construire une solution possible telle que le coût constitue une borne inférieure (on ne fixe aucune couleur à ce moment). Soit on colore tout en rouge et on obtient un coût de transmission nul mais un coût de re-coloration égal à $2$ (puisqu'on change la couleur des n\oe{}uds 19 et 23). Ce qui donne, pour \underline{$R$}$RRR$, un coût de $0,5 * 2 + 1 * 0 = 1$. Une autre possibilité est de tout colorer en vert, ce qui donne un coût de re-coloration nul et un coût de transmission de $0,45 + 0,45 + 1$. Ce qui donne, pour \underline{$V$}$VVV$, un coût total de $0,5 * 0 + 1 * 1 = 1$. Cette dernière solution est faisable puisque les n\oe{}uds 18 et 21 ont la même couleur et le n\oe{}ud 23 est bien dans la même couleur que sa contrainte. La solution $RRRR$, elle, n'est pas faisable puisque le n\oe{}ud 23 ne respecte pas sa contrainte. La dernière solution construite à la première étape est \underline{$O$}$VRV$ qui a un coût total de $1,4$. Cette solution n'est pas faisable puisque les n\oe{}uds 18 et 21 n'ont pas la même couleur. \\

À ce stade, l'\textit{incumbent} est fixé à $1$, grâce à la solution faisable \underline{$V$}$VVV$. Les deux autres solutions possibles n'ont pas de coût strictement inférieur à cet \textit{incumbent}, ce qui nous permet d'affirmer qu'il n'y aura pas de meilleure solution que celle trouvée. Nous pouvons donc arrêter la recherche et prendre $VVVV$ comme solution pour notre coloration, ce qui signifie que nous devons finir la coloration du nouveau graphe en colorant les n\oe{}uds 18, 19, 21 et 23 en vert. La figure de l'arbre de recherche est représenté en figure~\ref{figRedistribEx06}.

\begin{figure}[h!]
	\begin{center}
		\includegraphics[scale=0.5]{Images/figRedistribEx06.pdf}
		\caption{Les deux premières étapes de la re-coloration}
		\label{figRedistribEx06}
	\end{center}
\end{figure}

Les deux paramètres de la seconde partie (celle qui s'occupe de finir la re-coloration) ont été fixés de telle manière que le nombre de transmissions à minimiser est plus important que la conservation de la structure de distribution ($\beta$ valait $2 \alpha$). Par chance, dans cet exemple, le fait d'inverser les paramètres, c'est-à-dire de privilégier la conservation de la structure sur la minimisation des transmissions ne change pas la solution. Le lecteur doit se rendre compte que ce ne sera pas tout le temps le cas et que ces paramètres influent beaucoup sur la solution finale. \\

Cet exemple a donc permis de clarifier les étapes de la redistribution ainsi que d'aider à comprendre toutes les subtilités effectuées lors de ces différentes étapes. Nous pourrions vouloir étudier les variations des $\alpha$ et $\beta$ afin d'observer leur impact sur les solutions mais, dans cet exemple, cela ne changera rien. En effet, étant donné que la solution $RVRV$ a un coût de re-coloration nul et un coût de transmission égal à $0,45 + 0,1 + 0,45 = 1$, augmenter ou diminuer $\alpha$ ne fera pas varier la solution puisque son $C_r$ est nul. De plus, augmenter ou diminuer $\beta$ ne changera également pas la solution choisie puisqu'elle possèdera toujours le coût total le plus petit. \\

Pour se convaincre que $\alpha$ et $\beta$ agissent quand même sur la solution trouvée, prenons un autre exemple. Imaginons un graphe très simple, composé de trois n\oe{}uds. Un tel schéma est représenté en figure~\ref{figRedistribEx08}. 

\begin{figure}[h!]
	\begin{center}
		\includegraphics[scale=0.6]{Images/figRedistribEx08.pdf}
		\caption{Exemple très simple pour montrer l'implication des $\alpha$ et $\beta$}
		\label{figRedistribEx08}
	\end{center}
\end{figure}

Une contrainte existe sur le dernier n\oe{}ud, celui-ci doit être en vert. La table ci-dessous montre les calculs des coûts totaux de toutes les solutions avec $\alpha = 0,5$ et $\beta = 1$ en noir et, en vert entre parenthèses, les coûts totaux avec $\alpha = 1$ et $\beta = 0,5$. On peut s'apercevoir très facilement que la solution n'est pas la même selon les paramètres $\alpha$ et $\beta$ choisis. En effet, dans le premier choix de paramètres, la solution optimale serait $VVV$, tandis que dans le deuxième choix des paramètres, la solution optimale est $ROV$. \\

\begin{tabular}{| l  l || l l || l l |}
	\hline
	RRR: $1 + 0 = 1$ & ({\color{ForestGreen} 2}) & 
	ORR: $1,5 + 1 = 2,5$ & ({\color{ForestGreen} 3,5}) & 
	VRR: $1,5 + 1 = 2,5$ & ({\color{ForestGreen} 3,5}) \\
	\hline
	RRO: $1 + 1 = 2$ & ({\color{ForestGreen} 2,5}) &
	ORO: $1,5 + 2 = 3,5$ & ({\color{ForestGreen} 4}) &
	VRO: $1,5 + 2 = 3,5$ & ({\color{ForestGreen} 4}) \\
	\hline
	RRV: $0,5 + 1 = 1,5$ & ({\color{ForestGreen} 1,5}) &
	ORV: $1 + 2 = 3$ & ({\color{ForestGreen} 3}) &
	VRV: $1 + 2 = 3$ & ({\color{ForestGreen} 3}) \\
	\hline
	ROR: $0,5 + 1 = 1,5$ & ({\color{ForestGreen} 2}) &
	OOR: $1 + 1 = 2$ & ({\color{ForestGreen} 2,5}) &
	VOR: $1 + 2 = 3$ & ({\color{ForestGreen} 3}) \\
	\hline
	ROO: $0,5 + 1 = 1,5$ & ({\color{ForestGreen} 3}) &
	OOO: $1 + 0 = 1$ & ({\color{ForestGreen} 2}) &
	VOO: $1 + 1 = 2$ & ({\color{ForestGreen} 2,5}) \\
	\hline
	ROV: $0 + 2 = 2$ & ({\color{ForestGreen} 1}) &
	OOV: $0,5 + 1 = 1,5$ & ({\color{ForestGreen} 1,5}) &
	VOV: $0,5 + 2 = 2,5$ & ({\color{ForestGreen} 3}) \\
	\hline
	RVR: $1 + 2 = 3$ & ({\color{ForestGreen} 3}) &
	OVR: $1,5 + 2 = 3,5$ & ({\color{ForestGreen} 4}) &
	VVR: $1,5 + 1 = 2,5$ & ({\color{ForestGreen} 3,5}) \\
	\hline
	RVO: $1 + 2 = 3$ & ({\color{ForestGreen} 3}) &
	OVO: $1,5 + 2 = 3,5$ & ({\color{ForestGreen} 4}) &
	VVO: $1,5 + 1 = 2,5$ & ({\color{ForestGreen} 3,5}) \\
	\hline
	RVV: $0,5 + 1 = 1,5$ & ({\color{ForestGreen} 1,5}) &
	OVV: $1 + 1 = 2$ & ({\color{ForestGreen} 2,5}) &
	VVV: $1 + 0 = 1$ & ({\color{ForestGreen} 2}) \\
	\hline
\end{tabular}